package top.retain;

/**
 * @author ivorfan
 * @date 2021/8/3 22:37
 */
public class Circle {

    /**
     * 圆环上有10个点，编号为0~9。从0点出发，
     * 每次可以逆时针和顺时针走一步，问走n步回到0点共有多少种走法。
     */
    public static void main(String[] args) {
        System.out.println(method(10));
    }

    // 走n-1步到1到步数+走n-1步到9到步数
    // dp[i][j] : 走i步到j到方案数
    // d[i][j] = dp[i-1][(j + 1) % 10] + dp[i-1][(j - 1 + 10) % 10]
    public static int method(int n) {
        if (n % 2 != 0) return 0;
        int[][] dp =new int[n + 1][10];
        dp[2][0] = 2;
        for (int i = 1; i <= n; i++) {
          dp[i][i] = 1;
          dp[i][10- i] = 1;
        }
        dp[1][9] = 1;
        for (int i = 2; i <= n; i++) {
          for (int j = 0; j < i; j++) {
            dp[i][j] = dp[i - 1][(j -1 + 10) % 10] + dp[i-1][(j + 1) % 10];
          }
        }
        return dp[n][0];
    }

}
